#include <iostream>
#include <memory>
#include <vector>
#include <string>
#include <string>
#include <fstream>
#include <streambuf>
#include <sstream>
#include <cstdlib>
#include <new>
#include <typeinfo>
#include <list>
#include <thread> // std::thread
#include <mutex>  // std::mutex
#include <unodered_map>

using namespace std;

// chapter 0

// 学习数据结构和算法的框架思维
// 这是好久之前的一篇文章「学习数据结构和算法的框架思维」的修订版。之前那篇文章收到广泛好评，没看过也没关系，这篇文章会涵盖之前的所有内容，并且会举很多代码的实例，教你如何使用框架思维。

// 首先，这里讲的都是普通的数据结构，咱不是搞算法竞赛的，野路子出生，我只会解决常规的问题。另外，以下是我个人的经验的总结，没有哪本算法书会写这些东西，所以请读者试着理解我的角度，别纠结于细节问题，因为这篇文章就是希望对数据结构和算法建立一个框架性的认识。

// 从整体到细节，自顶向下，从抽象到具体的框架思维是通用的，不只是学习数据结构和算法，学习其他任何知识都是高效的。

// 一、数据结构的存储方式
// 数据结构的存储方式只有两种：数组（顺序存储）和链表（链式存储）。

// 这句话怎么理解，不是还有散列表、栈、队列、堆、树、图等等各种数据结构吗？

// 我们分析问题，一定要有递归的思想，自顶向下，从抽象到具体。你上来就列出这么多，那些都属于「上层建筑」，而数组和链表才是「结构基础」。因为那些多样化的数据结构，究其源头，都是在链表或者数组上的特殊操作，API 不同而已。

// 比如说「队列」、「栈」这两种数据结构既可以使用链表也可以使用数组实现。用数组实现，就要处理扩容缩容的问题；用链表实现，没有这个问题，但需要更多的内存空间存储节点指针。

// 「图」的两种表示方法，邻接表就是链表，邻接矩阵就是二维数组。邻接矩阵判断连通性迅速，并可以进行矩阵运算解决一些问题，但是如果图比较稀疏的话很耗费空间。邻接表比较节省空间，但是很多操作的效率上肯定比不过邻接矩阵。

// 「散列表」就是通过散列函数把键映射到一个大数组里。而且对于解决散列冲突的方法，拉链法需要链表特性，操作简单，但需要额外的空间存储指针；线性探查法就需要数组特性，以便连续寻址，不需要指针的存储空间，但操作稍微复杂些。

// 「树」，用数组实现就是「堆」，因为「堆」是一个完全二叉树，用数组存储不需要节点指针，操作也比较简单；用链表实现就是很常见的那种「树」，因为不一定是完全二叉树，所以不适合用数组存储。为此，在这种链表「树」结构之上，又衍生出各种巧妙的设计，比如二叉搜索树、AVL 树、红黑树、区间树、B 树等等，以应对不同的问题。

// 了解 Redis 数据库的朋友可能也知道，Redis 提供列表、字符串、集合等等几种常用数据结构，但是对于每种数据结构，底层的存储方式都至少有两种，以便于根据存储数据的实际情况使用合适的存储方式。

// 综上，数据结构种类很多，甚至你也可以发明自己的数据结构，但是底层存储无非数组或者链表，二者的优缺点如下：

// 数组由于是紧凑连续存储,可以随机访问，通过索引快速找到对应元素，而且相对节约存储空间。但正因为连续存储，内存空间必须一次性分配够，所以说数组如果要扩容，需要重新分配一块更大的空间，再把数据全部复制过去，时间复杂度 O(N)；而且你如果想在数组中间进行插入和删除，每次必须搬移后面的所有数据以保持连续，时间复杂度 O(N)。

// 链表因为元素不连续，而是靠指针指向下一个元素的位置，所以不存在数组的扩容问题；如果知道某一元素的前驱和后驱，操作指针即可删除该元素或者插入新元素，时间复杂度 O(1)。但是正因为存储空间不连续，你无法根据一个索引算出对应元素的地址，所以不能随机访问；而且由于每个元素必须存储指向前后元素位置的指针，会消耗相对更多的储存空间。

// 二、数据结构的基本操作
// 对于任何数据结构，其基本操作无非遍历 + 访问，再具体一点就是：增删查改。

// 数据结构种类很多，但它们存在的目的都是在不同的应用场景，尽可能高效地增删查改。话说这不就是数据结构的使命么？

// 如何遍历 + 访问？我们仍然从最高层来看，各种数据结构的遍历 + 访问无非两种形式：线性的和非线性的。

// 线性就是 for/while 迭代为代表，非线性就是递归为代表。再具体一步，无非以下几种框架：

// 数组遍历框架，典型的线性迭代结构：

void traverse(vector<int> vec)
{
    for (int i = 0; i < vec.size() - 1; i++)
    {
    }
}

// 链表遍历框架，兼具迭代和递归结构:
class ListNode
{
    int val;
    ListNode next;
}

void traverse(ListNode head)
{
    for (ListNode p = head; p != null; p = p.next)
    {
    }
}

// 递归访问 head.val
void traverse(ListNode head)
{
    traverse(head.next)
}

// 二叉树遍历框架，典型的非线性递归遍历结构：
class TreeNode
{
    int val;
    TreeNode left, right;
};

// 前序遍历：根结点 ---> 左子树 ---> 右子树
// 中序遍历：左子树---> 根结点 ---> 右子树
// 后序遍历：左子树 ---> 右子树 ---> 根结点
// 层次遍历：只需按层次遍历即可  // BFS使用queue

void traverse(TreeNode root)
{
    //  前序遍历
    traverse(root.left);
    // 中序
    traverse(root.right);
    // 后序
}

// 你看二叉树的递归遍历方式和链表的递归遍历方式，相似不？再看看二叉树结构和单链表结构，相似不？如果再多几条叉，N 叉树你会不会遍历？
// 二叉树框架可以扩展为 N 叉树的遍历框架：
/* 基本的 N 叉树节点 */
class TreeNode
{
    int val;
    TreeNode[] children;
};

void traverse(TreeNode root)
{
    for (TreeNode child : root.children)
    {
        traverse(child);
    }
}

// N 叉树的遍历又可以扩展为图的遍历，因为图就是好几 N 叉棵树的结合体。你说图是可能出现环的？这个很好办，用个布尔数组 visited 做标记就行了，这里就不写代码了
// 所谓框架，就是套路。不管增删查改，这些代码都是永远无法脱离的结构，你可以把这个结构作为大纲，根据具体问题在框架上添加代码就行了，下面会具体举例

// 刷二叉树看到题目没思路？根据很多读者的问题，其实大家不是没思路，只是没有理解我们说的「框架」是什么。不要小看这几行破代码，几乎所有二叉树的题目都是一套这个框架就出来了。
void traverse(TreeNode root)
{
    //  前序遍历
    traverse(root.left);
    // 中序
    traverse(root.right);
    // 后序
}

///////////////////////////////////////////////////////////////////////////////////////
// 重叠子问题、最优子结构、状态转移方程就是动态规划三要素。具体什么意思等会会举例详解，但是在实际的算法问题中，写出状态转移方程是最困难的，
// 这也就是为什么很多朋友觉得动态规划问题困难的原因
// 递归算法的时间复杂度怎么计算？子问题个数乘以解决一个子问题需要的时间。
// 子问题个数，即递归树中节点的总数。显然二叉树节点总数为指数级别，所以子问题个数为 O(2^n)。
// 解决一个子问题的时间，在本算法中，没有循环，只有 f(n - 1) + f(n - 2) 一个加法操作，时间为 O(1)

//////////////////////////////////////////////////////////////////////////////////////
// 问题
// 编辑距离
// 给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 
// 你可以对一个单词进行如下三种操作:
// 插入一个字符
// 删除一个字符
// 替换一个字符

// 示例 1：
// 输入：word1 = "horse", word2 = "ros"
// 输出：3
// 解释：
// horse -> rorse (将 'h' 替换为 'r')
// rorse -> rose (删除 'r')
// rose -> ros (删除 'e')

// https://github.com/labuladong/fucking-algorithm/blob/master/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%B3%BB%E5%88%97/%E7%BC%96%E8%BE%91%E8%B7%9D%E7%A6%BB.md
class Solution
{
public:
    int minDistance(string s1, string s2)
    {
        int m = s1.size();
        int n = s2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (int i = 1; i <= m; i++)
            dp[i][0] = i; // base case: 当s2为空，s1需要删除所有字符才能与s2相等
        for (int j = 1; j <= n; j++)
            dp[0][j] = j; // base case: 当s1为空, s1需要不断插入新字符才能与s2相等
        //自底向上求解
        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (s1[i - 1] == s2[j - 1])
                { // 两个字符串当前的字符一样  // 啥都别做（skip）i, j 同时向前移动
                    dp[i][j] = dp[i - 1][j - 1];
                }
                else                                        // 两个字符串当前的字符不同
                                                            //使得s1[0:i]和s2[0:j]相同的最短编辑距离可通过插入，删除或替换三种操作其中一种得到
                    dp[i][j] = min({dp[i - 1][j] + 1,       // 删除s1[i]这个字符
                                    dp[i][j - 1] + 1,       // 在s1[i]后面加一个和s2[j]相同的字符  // 我直接在 s1[i] 插入一个和 s2[j] 一样的字符,那么 s2[j] 就被匹配了，前移 j，继续跟 i 对比,别忘了操作数加一
                                    dp[i - 1][j - 1] + 1}); // 将s1[i]的字符替换为s2[j]的字符
            }
        }
        //储存着整个 s1 和 s2 的最小编辑距离
        return dp[m][n];
    }
};

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// 二分查找框架
int binarySearch(int[] nums, int target)
{
    int left = 0, right = ...;

    while (...)
    {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target)
        {
            ...
        }
        else if (nums[mid] < target)
        {
            left = ...
        }
        else if (nums[mid] > target)
        {
            right = ...
        }
    }
    return ...;
}

// https://github.com/labuladong/fucking-algorithm/blob/master/%E9%AB%98%E9%A2%91%E9%9D%A2%E8%AF%95%E7%B3%BB%E5%88%97/koko%E5%81%B7%E9%A6%99%E8%95%89.md
// 如何运用二分查找算法
// 最常见的就是教科书上的例子，在有序数组中搜索给定的某个目标值的索引。再推广一点，如果目标值存在重复，修改版的二分查找可以返回目标值的左侧边界索引或者右侧边界索引
// 注意这个 for 循环，就是在连续的空间线性搜索，这就是二分查找可以发挥作用的标志

// 传送带上的包裹必须在 D 天内从一个港口运送到另一个港口
// 传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。
// 返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。
// 示例 1：
// 输入：weights = [1,2,3,4,5,6,7,8,9,10], D = 5
// 输出：15
// 解释：
// 船舶最低载重 15 就能够在 5 天内送达所有包裹，如下所示：
// 第 1 天：1, 2, 3, 4, 5
// 第 2 天：6, 7
// 第 3 天：8
// 第 4 天：9
// 第 5 天：10

// 请注意，货物必须按照给定的顺序装运，因此使用载重能力为 14 的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10)

// 寻找左侧边界的二分查找
int shipWithinDays(vector<int> weight, int D)
{
    int left = max(weight);      // 载重可能的最小值
    int right = sum(weight) + 1; // 载重可能的最大值 + 1
    while (left < right)
    {
        int mid = (left + right) / 2;
        if (canFinshih(weight, D, mid)
        {
            right = mid;
        }
    }
}

// 如果载重为 cap，是否能在 D 天内运完货物？
bool canFinshih(vector<int> w, int D, int cap)
{
    int i = 0;
    for (int day = 0; day < D; day++)
    {
        int max_cap = cap;
        while (max_cap -= w[i] > 0)
        {
            i++;
        }
        if (i == w.size())
        {
            return true;
        }
    }
    return false;
}

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// https://github.com/labuladong/fucking-algorithm/blob/master/%E9%AB%98%E9%A2%91%E9%9D%A2%E8%AF%95%E7%B3%BB%E5%88%97/%E6%8E%A5%E9%9B%A8%E6%B0%B4.md
// 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

// 位置 i 能达到的水柱高度和其左边的最高柱子、右边的最高柱子有关，我们分别称这两个柱子高度为 l_max 和 r_max；位置 i 最大的水柱高度就是 min(l_max, r_max)
int trap(vector<int> height)
{
    int res = 0;
    int n = height.size();
    for (int i = 0; i < n - 1; i++)
    {
        int max_l;
        int max_r;
        // 左边的最高
        for (int j = i; j >= 0; j--)
        {
            max_l = max(height[j]);
        }

        // 右边的最高
        for (int k = i; j <= n - 1; k--)
        {
            max_r = max(height[k]);
        }

        res += min(max_l, max_r) - height[i];
    }
    return res;
}

////////////////////////////////////////////////////////////////////////////////////
// https://github.com/labuladong/fucking-algorithm/blob/master/%E9%AB%98%E9%A2%91%E9%9D%A2%E8%AF%95%E7%B3%BB%E5%88%97/%E5%A6%82%E4%BD%95%E5%8E%BB%E9%99%A4%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E9%87%8D%E5%A4%8D%E5%85%83%E7%B4%A0.md
// LeetCode - 数组 - 删除有序数组重复元素 算法 java 发布于 2019 - 03 - 01 题目描述 给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

//  不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成
//  给定数组 nums = [ 1, 1, 2 ]
//  函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2
//  我们让慢指针 slow 走左后面，快指针 fast 走在前面探路，找到一个不重复的元素就告诉 slow 并让 slow 前进一步。这样当 fast 指针遍历完整个数组 nums 后，nums[0..slow] 就是不重复元素，之后的所有元素都是重复元素
// 双指针

int removeDuplicates(int[] nums)
{
    int slow = 0;
    int fast = 1;
    while (fast < nums.length)
    {
    if(nums[fast]!=nums[slow]])
    {
        slow++;
        num[slow] = num[fast];
    }
    fast++;
    }
    return slow += 1; // 长度为索引 + 1
}

ListNode deleteDuplicates(ListNode *head)
{
    ListNode *slow = head;
    ListNode *fast = head->next;
    while (fast != nullptr)
    {
        if (fast->val != slow->val)
        {
            slow.next = fast;
            slow = slow->next;
        }
        fast++;
    }
    slow.next = nullptr;
    return slow;
}

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// 05 longest palindromic substring(M)
//最大回文子串：分两种情况，回文子串长度为偶数和奇数：奇数的话直接向两边搜索，偶数的话和下一个数一起向两边搜索
// https://github.com/labuladong/fucking-algorithm/blob/master/%E9%AB%98%E9%A2%91%E9%9D%A2%E8%AF%95%E7%B3%BB%E5%88%97/%E6%9C%80%E9%95%BF%E5%9B%9E%E6%96%87%E5%AD%90%E4%B8%B2.md
// 双指针

string palindrome(string &s, int l, int r)
{
    // 防止索引越界
    while (l >= 0 && r < s.size() && s[l] == s[r])
    {
        // 向两边展开
        l--;
        r++;
    }
    // 返回以 s[l] 和 s[r] 为中心的最长回文串
    return s.substr(l + 1, r - l - 1);
}

string longestPalindrome(string s)
{
    string res;
    for (int i = 0; i < s.size(); i++)
    {
        // 以 s[i] 为中心的最长回文子串
        string s1 = palindrome(s, i, i);
        // 以 s[i] 和 s[i+1] 为中心的最长回文子串
        string s2 = palindrome(s, i, i + 1);
        // res = longest(res, s1, s2)
        res = res.size() > s1.size() ? res : s1;
        res = res.size() > s2.size() ? res : s2;
    }
    return res;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// 11 valid parenthese 验证括号(E)
// 使用栈，如果为左括号，就将其入栈，如果遇到右括号，就拿出栈顶元素比较
bool isValid(string s)
{
    stack<char> parenthese;
    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] == '(' || s[i] == '[' || s[i] == '{')
        {
            parenthese.push(s[i]);
        }
        else
        {
            if (parenthese.empty())
            {
                return false;
            }
            if (s[i] == ')' && parenthese.top() != '(')
                return false;
            if (s[i] == '}' && parenthese.top() != '{')
                return false;
            if (s[i] == ']' && parenthese.top() != '[')
                return false;
            parenthese.pop();
        }
    }
    return parenthese.empty();
}

//////////////////////////////////////////////////////////////////////////////////////
// https://github.com/labuladong/fucking-algorithm/blob/master/%E9%AB%98%E9%A2%91%E9%9D%A2%E8%AF%95%E7%B3%BB%E5%88%97/k%E4%B8%AA%E4%B8%80%E7%BB%84%E5%8F%8D%E8%BD%AC%E9%93%BE%E8%A1%A8.md
// 如何k个一组反转链表
// 之前的文章「递归反转链表的一部分」讲了如何递归地反转一部分链表，有读者就问如何迭代地反转链表，这篇文章解决的问题也需要反转链表的函数，我们不妨就用迭代方式来解决。

// 本文要解决「K 个一组反转链表」

class Solution
{
public:
    ListNode *reverseKGroup(ListNode *head, int k)
    {
        if (!head)
            return head;
        ListNode *begin = head;
        ListNode *end = head;
        for (int i = 0; i < k; ++i)
        {
            if (!end)
                return head;
            end = end->next;
        }
        ListNode *newHead = reverse(begin, end);
        begin->next = reverseKGroup(end, k);
        return newHead;
    }

private:
    ListNode *reverse(ListNode *begin, ListNode *end)
    {
        ListNode *newHead = nullptr;
        ListNode *cur = begin;
        while (cur != end)
        {
            ListNode *next = cur->next;
            cur->next = newHead;
            newHead = cur;
            cur = next;
        }
        return newHead;
    }
};

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// https://github.com/labuladong/fucking-algorithm/blob/master/%E9%AB%98%E9%A2%91%E9%9D%A2%E8%AF%95%E7%B3%BB%E5%88%97/%E6%B6%88%E5%A4%B1%E7%9A%84%E5%85%83%E7%B4%A0.md
// 给定一个包含0,1,2,3,…,n中n个数的序列，找出0, …, n中没有出现在序列中的那个数。
// 解析：
// 给⼀个⻓度为 n 的数组， 其索引应该在 [0,n) ， 但是现在你要装进去 n + 1 个元素 [0,n] ， 那么肯定有⼀个元素装不下嘛， 请你找出这个缺失的元素
// 如何找这个落单的数字呢，只要把所有的元素和索引做异或运算，成对儿的数字都会消为 0，只有这个落单的元素会剩下，也就达到了我们的目的。

int missingNumber(int[] nums)
{
    int n = nums.length;
    int res = 0;
    // 先和新补的索引异或一下
    res ^= n;
    // 和其他的元素、索引做异或
    for (int i = 0; i < n; i++)
        res ^= i ^ nums[i];
    return res;
}

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// 判断回文链表
// 寻找回文串的核心思想是从中心向两端扩展：

string palindrome(string &s, int l, int r)
{
    // 防止索引越界
    while (l >= 0 && r < s.size() && s[l] == s[r])
    {
        // 向两边展开
        l--;
        r++;
    }
    // 返回以 s[l] 和 s[r] 为中心的最长回文串
    return s.substr(l + 1, r - l - 1);
}
// 因为回文串长度可能为奇数也可能是偶数，长度为奇数时只存在一个中心点，而长度为偶数时存在两个中心点，所以上面这个函数需要传入l和r
// 而判断一个字符串是不是回文串就简单很多，不需要考虑奇偶情况，只需要「双指针技巧」，从两端向中间逼近即可：

bool isPalindrome(string s)
{
    int left = 0, right = s.length - 1;
    while (left < right)
    {
        if (s[left] != s[right])
            return false;
        left++;
        right--;
    }
    return true;
}
// 以上代码很好理解吧，因为回文串是对称的，所以正着读和倒着读应该是一样的，这一特点是解决回文串问题的关键。
// 下面扩展这一最简单的情况，来解决：如何判断一个「单链表」是不是回文。

////////////////////////////////////////////////////////////////////////////////////////////
// 双指针技巧总结
// 我把双指针技巧再分为两类，一类是「快慢指针」，一类是「左右指针」。前者解决主要解决链表中的问题，比如典型的判定链表中是否包含环；后者主要解决数组（或者字符串）中的问题，比如二分查找。
// 1、判定链表中是否含有环
// 2、已知链表中含有环，返回这个环的起始位置
// 3、寻找链表的中点
// 4、寻找链表的倒数第 k 个元素
// 二、左右指针的常用算法
// 1、二分查找
// 2、两数之和
// 3、反转数组

/////////////////////////////////////////////////////////////
// 滑动窗口技巧
// 动窗口算法
// 这也许是双指针技巧的最高境界了，如果掌握了此算法，可以解决一大类子字符串匹配的问题
// 我们可以总结出滑动窗口算法的抽象思想：
int left = 0;
int right = 0;
while (right < s.size())
{
    window.add(s[right]);
    right++;

    while (valid)
    {
        window.remove(s[left]);
        left++;
    }
}

// 本文详解「滑动窗口」这种高级双指针技巧的算法框架   // 子字符串匹配

// 题目描述:
// 给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。
// 示例:
// 输入: S = "ADOBECODEBANC", T = "ABC"
// 输出: "BANC"

//滑动窗口算法的思路是这样:
// 1、我们在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引闭区间 [left, right] 称为一个「窗口」。
// 2、我们先不断地增加 right 指针扩大窗口 [left, right]，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。
// 3、此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right]，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新一轮结果。
// 4、重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。

// source 中是否包括target
bool helper(string source, string target){};

// 双指针的框架
int left = 0;
int right = 0;
string source;
string window;
int res_length = source.size();
while (right < source.size())
{
    right++;
    window.add(source[right]);
    if (window is valid)
    {
        res_length = min(res_length, window.size());
        window.remove(source[left]);
        left++;
    }
}

// 更加优雅的解法
string minWindow(string s, string t)
{
    // 记录最短子串的开始位置和长度
    int start = 0;
    int minLen = INT_MAX;
    int left = 0;
    int right = 0;
    unordered_map<char, int> window;
    unordered_map<char, int> needs;
    for (char c : t)
    {
        needs[c]++;
    }
    int match = 0;
    while (right < s.size())
    {
        char c1 = s[right];
        if (needs.count(c1))
        {
            window[c1]++;
            if (window[c1] == needs[c1])
                match++;
        }
        right++;

        while (match == needs.size())
        {
            if (right - left < minLen)
            {
                // 更新最小子串的位置和长度
                start = left;
                minLen = right - left;
            }
            char c2 = s[left];
            if (needs.count(c2))
            {
                window[c2]--;
                if (window[c2] < needs[c2])
                    match--;
            }
            left++;
        }
    }
    return minLen == INT_MAX ? "" : s.substr(start, minLen);
}

// 无重复字符的最长子串
int lengthOfLongestSubstring(string s)
{
    int left = 0;
    int right = s.size();
}

///////////////////////////////////////////////////////////////////////////////////////////////////
// 递归详解
// 递归的基本思想是某个函数直接或者间接地调用自身，这样就把原问题的求解转换为许多性质相同但是规模更小的子问题。我们只需要关注如何把原问题划分成符合条件的子问题，而不需要去研究这个子问题是如何被解决的。递归和枚举的区别在于：枚举是横向地把问题划分，然后依次求解子问题，而递归是把问题逐级分解，是纵向的拆分。

// 以下会举例说明我对递归的一点理解，如果你不想看下去了，请记住这几个问题怎么回答：

// 如何给一堆数字排序？ 答：分成两半，先排左半边再排右半边，最后合并就行了，至于怎么排左边和右边，请重新阅读这句话。
// 孙悟空身上有多少根毛？ 答：一根毛加剩下的毛。
// 你今年几岁？ 答：去年的岁数加一岁,1999 年我出生。
// 递归代码最重要的两个特征：结束条件和自我调用。自我调用是在解决子问题，而结束条件定义了最简子问题的答案

// 给一课二叉树，和一个目标值，节点上的值有正有负，返回树中和等于目标值的路径条数，让你编写 pathSum 函数：
/* 有了以上铺垫，详细注释一下代码 */
int pathSum(TreeNode root, int sum)
{
    if (root == null)
        return 0;
    int pathImLeading = count(root, sum);        // 自己为开头的路径数
    int leftPathSum = pathSum(root.left, sum);   // 左边路径总数（相信他能算出来）
    int rightPathSum = pathSum(root.right, sum); // 右边路径总数（相信他能算出来）
    return leftPathSum + rightPathSum + pathImLeading;
}
int count(TreeNode node, int sum)
{
    if (node == null)
        return 0;
    // 我自己能不能独当一面，作为一条单独的路径呢？
    int isMe = (node.val == sum) ? 1 : 0;
    // 左边的小老弟，你那边能凑几个 sum - node.val 呀？
    int leftBrother = count(node.left, sum - node.val);
    // 右边的小老弟，你那边能凑几个 sum - node.val 呀？
    int rightBrother = count(node.right, sum - node.val);
    return isMe + leftBrother + rightBrother; // 我这能凑这么多个
}

/////////////////////////////////////////////////////////////////////////////////////////////////////
// 二叉搜索树操作集锦
void traverse(TreeNode root)
{
    // 中序
    traverse(root.left);
    // 前序
    traverse(root.right);
    // 后序
}

// 通过这篇文章，你学会了如下几个技巧:
// 二叉树算法设计的总路线：把当前节点要做的事做好，其他的交给递归框架，不用当前节点操心
// 如果当前节点会对下面的子节点有整体影响，可以通过辅助函数增长参数列表，借助参数传递信息
// 在二叉树框架之上，扩展出一套 BST 遍历框架:
void BST(TreeNode root, int target)
{
    if (root.val == target)
        // 找到目标，做点什么
        if (root.val < target)
            BST(root.right, target);
    if (root.val > target)
        BST(root.left, target);
}

// 1. 如何把二叉树所有的节点中的值加一？
void plusOne(TreeNode root)
{
    if (root == null)
        return;
    root.val += 1;

    plusOne(root.left);
    plusOne(root.right);
}

// 2. 如何判断两棵二叉树是否完全相同？
boolean isSameTree(TreeNode root1, TreeNode root2)
{
    // 都为空的话，显然相同
    if (root1 == null && root2 == null)
        return true;
    // 一个为空，一个非空，显然不同
    if (root1 == null || root2 == null)
        return false;
    // 两个都非空，但 val 不一样也不行
    if (root1.val != root2.val)
        return false;

    // root1 和 root2 该比的都比完了
    return isSameTree(root1.left, root2.left) && isSameTree(root1.right, root2.right);
}

// 二叉搜索树（Binary Search Tree，简称 BST）是一种很常用的的二叉树。它的定义是：一个二叉树中，任意节点的值要大于等于左子树所有节点的值，且要小于等于右边子树的所有节点的值

// 求一棵二叉树的最大值
int maxVal(TreeNode root)
{
    if (root == null)
        return -1;
    int left = maxVal(root.left);
    int right = maxVal(root.right);
    return max(root.val, left, right);
}

// 判断 BST 的合法性
bool isValidBST(TreeNode *root)
{
    return isValid(root, INT_MIN, INT_MAX);
}

bool isValid(TreeNode *root, int low, int high)
{
    if (root == NULL)
        return true;
    return root->val > low && root->val < high && isValid(root->left, low, root->val) && isValid(root->right, root->val, high);
}

// 在 BST 中查找一个数是否存在
boolean isInBST(TreeNode root, int target)
{
    if (root == null)
        return false;
    if (root.val == target)
        return true;
    if (root.val < target)
        return isInBST(root.right, target);
    if (root.val > target)
        return isInBST(root.left, target);
    // root 该做的事做完了，顺带把框架也完成了，妙
}

// 在 BST 中插入一个数
TreeNode insertIntoBST(TreeNode root, int val)
{
    // 找到空位置插入新节点
    if (root == null)
        return new TreeNode(val);
    // if (root.val == val)
    //     BST 中一般不会插入已存在元素
    if (root.val < val)
        root.right = insertIntoBST(root.right, val);
    if (root.val > val)
        root.left = insertIntoBST(root.left, val);
    return root;
}

// 在 BST 中删除一个数
TreeNode deleteNode(TreeNode root, int key)
{
    if (root.val == key)
    {
        // 找到啦，进行删除
    }
    else if (root.val > key)
    {
        root.left = deleteNode(root.left, key);
    }
    else if (root.val < key)
    {
        root.right = deleteNode(root.right, key);
    }
    return root;
}

// 如何删除?
TreeNode deleteNode(TreeNode root, int key)
{
    if (root == null)
        return null;
    if (root.val == key)
    {
        // 这两个 if 把情况 1 和 2 都正确处理了
        if (root.left == null)
            return root.right;
        if (root.right == null)
            return root.left;
        // 处理情况 3
        TreeNode minNode = getMin(root.right);
        root.val = minNode.val;
        root.right = deleteNode(root.right, minNode.val);
    }
    else if (root.val > key)
    {
        root.left = deleteNode(root.left, key);
    }
    else if (root.val < key)
    {
        root.right = deleteNode(root.right, key);
    }
    return root;
}

TreeNode getMin(TreeNode node)
{
    // BST 最左边的就是最小的
    while (node.left != null)
        node = node.left;
    return node;
}

////////////////////////////////////////////////////////////////////////////////////////////////
// DP // dp[i][j] = max{dp[i][j-1],dp[i-1][j]};

// 斐波那契数列
// 1、暴力递归
// 斐波那契数列的数学形式就是递归的，写成代码就是这样:

int fib(int N)
{
    if (N == 1 || N == 2)
        return 1;
    return fib(N - 1) + fib(N - 2);
}

// // DP
int fib(int N)
{
    vector<int> dp(N + 1, 0);
    // base case
    dp[1] = dp[2] = 1;
    for (int i = 3; i <= N; i++)
        dp[i] = dp[i - 1] + dp[i - 2];
    return dp[N];
}

// 先看下题目：给你 k 种面值的硬币，面值分别为 c1, c2 ... ck，每种硬币的数量无限，再给一个总金额 amount，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1
// https://github.com/lucianzhong/fucking-algorithm/blob/master/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%B3%BB%E5%88%97/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E8%AF%A6%E8%A7%A3%E8%BF%9B%E9%98%B6.md
int coinChange(vector<int> &coins, int amount)
{
    // dp[i] = x 表示，当目标金额为 i 时，至少需要 x 枚硬币
    vector<int> DP(amount + 1, amount + 1); // 数组大小为amount+1,初始值也为amount+1
    DP[0] = 0;
    for (int i = 0; i < amount + 1; i++)
    {
        for (coin : coins)
        {
            if ((i - coin) < 0)
            {
                continue;
            }

            DP[i] = min(DP[i], DP[i - coin] + 1);
        }
    }
    return DP[amount];
}

// 动态规划之子序列问题解题模板
// 子序列问题是常见的算法问题，而且并不好解决
// 首先，子序列问题本身就相对子串、子数组更困难一些，因为前者是不连续的序列，而后两者是连续的，就算穷举你都不一定会，更别说求解相关的算法问题了
// 而且，子序列问题很可能涉及到两个字符串，比如前文「最长公共子序列」，如果没有一定的处理经验，真的不容易想出来。所以本文就来扒一扒子序列问题的套路，其实就有两种模板，相关问题只要往这两种思路上想，十拿九稳
// 一般来说，这类问题都是让你求一个最长子序列，因为最短子序列就是一个字符嘛，没啥可问的。一旦涉及到子序列和最值，那几乎可以肯定，考察的是动态规划技巧，时间复杂度一般都是 O(n ^ 2)
// 原因很简单，你想想一个字符串，它的子序列有多少种可能？起码是指数级的吧，这种情况下，不用动态规划技巧，还想怎么着？
// 既然要用动态规划，那就要定义 dp 数组，找状态转移关系。我们说的两种思路模板，就是 dp 数组的定义思路。不同的问题可能需要不同的 dp 数组定义来解决。
// 一、两种思路
// 1、第一种思路模板是一个一维的 dp 数组:

int n = array.length;
int[] dp = new int[n];
for (int i = 1; i < n; i++)
{
    for (int j = 0; j < i; j++)
    {
        dp[i] = 最值(dp[i], dp[j] + ...)
    }
}
// 举个我们写过的例子「最长递增子序列」，在这个思路中 dp 数组的定义是:
// 在子数组 array[0..i] 中，我们要求的子序列（最长递增子序列）的长度是 dp[i]。

// 为啥最长递增子序列需要这种思路呢？前文说得很清楚了，因为这样符合归纳法，可以找到状态转移的关系，这里就不具体展开了。

// 2、第二种思路模板是一个二维的 dp 数组:
int n = arr.length;
int[][] dp = new dp[n][n];
for (int i = 0; i < n; i++)
{
    for (int j = 0; j < n; j++)
    {
        if (arr[i] == arr[j])
            dp[i][j] = dp[i][j] + ... else dp[i][j] = 最值(...)
    }
}

// 最长回文子序列
// 在子串 s[i..j] 中，最长回文子序列的长度为 dp[i][j]
// 子序列的问题将比子串更复杂，因为它是可以不连续的
int longestPalindromeSubseq(string s)
{
    int n = s.size();
    // dp 数组全部初始化为 0
    vector<vector<int>> dp(n, vector<int>(n, 0));
    // base case
    for (int i = 0; i < n; i++)
        dp[i][i] = 1;
    // 反着遍历保证正确的状态转移
    for (int i = n - 1; i >= 0; i--)
    {
        for (int j = i + 1; j < n; j++)
        {
            // 状态转移方程
            if (s[i] == s[j]) // // 它俩一定在最长回文子序列中
                dp[i][j] = dp[i + 1][j - 1] + 2;
            else
                // // s[i+1..j] 和 s[i..j-1] 谁的回文子序列更长？
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
        }
    }
    // 整个 s 的最长回文子串长度
    return dp[0][n - 1];
}

///////////////////////////////////////////////////////////////////////////////
// 回溯算法详解
// 废话不多说，直接上回溯算法框架。解决一个回溯问题，实际上就是一个决策树的遍历过程。你只需要思考 3 个问题：
// 1、路径：也就是已经做出的选择
// 2、选择列表：也就是你当前可以做的选择。
// 3、结束条件：也就是到达决策树底层，无法再做选择的条件
// 如果你不理解这三个词语的解释，没关系，我们后面会用「全排列」和「N 皇后问题」这两个经典的回溯算法问题来帮你理解这些词语是什么意思，现在你先留着印象。
// 代码方面，回溯算法的框架：

// result = []
// def backtrack(路径, 选择列表):
//     if 满足结束条件:
//         result.add(路径)
//         return

//     for 选择 in 选择列表:
//         做选择
//         backtrack(路径, 选择列表)
//         撤销选择

// 回溯算法就是个多叉树的遍历问题，关键就是在前序遍历和后序遍历的位置做一些操作，算法框架如下：

// def backtrack(...):
//     for 选择 in 选择列表:
//         做选择
//         backtrack(...)
//         撤销选择

// 全排序
typedef vector<int> track;
vector<track> res;
void backtrack(vector<int> nums, track)
{
    if (nums.size() == track.size()) // 满足结束条件,nums 中的元素全都在 track 中出现
    {
        res.push_back(track);
        return;
    }
    // 选择列表
    for (int i = 0; i < nums.size(); i++)
    {
        if (track.find(nums[i]))
        {
            continue; //已经作出了选择,跳过
        }
        else
        {
            track.push_back(nums[i]);
        }
        track.push_back(nums[i]);
        backtrack(nums, track); // 作出选择
        track.pop_back();       //  撤销选择
    }
}

// N 皇后问题
// 这个问题很经典了，简单解释一下：给你一个 N×N 的棋盘，让你放置 N 个皇后，使得它们不能互相攻击
// PS：皇后可以攻击同一行、同一列、左上左下右上右下四个方向的任意单位
// 这个问题本质上跟全排列问题差不多，决策树的每一层表示棋盘上的每一行；每个节点可以做出的选择是，在该行的任意一列放置一个皇后

vector<vector<string>> res;
int colum;
void backtrack(vector<string> board, int row)
{
    // 触发结束条件
    if (row == boad.size())
    {
        res.push_back(board);
        return;
    }

    int colum = board[row].size();
    // 选择列表
    for (int i = 0; i < colum; i++)
    {
        if (board.find(i)))
            {
                continue; //已经做过了选择,略过
            }
        // 排除不合法选择
        if (!isValid(board, row, col))
            continue;
        board.push_back(colum);    //做选择
        backtrack(board, row + 1); // 回溯,进入下一行决策
        board.pop_back();          // 撤销选择
    }
}

////////////////////////////////////////////////////////////////////////////
// 动态规划设计：最长递增子序列
// 注意「子序列」和「子串」这两个名词的区别，子串一定是连续的，而子序列不一定是连续的

int lengthOfLIS(vector<int> nums)
{
    vector<int> DP(nums.size(), 1);
    for (int i = 0; i < nums.size(); i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (nums[j] < nums[i])
            {
                DP[i] = max(DP[i], DP[j] + 1); // 当前的num[i]和它之前所有的最长递增子序列的长度
            }
        }
    }
}

// 更加优雅的解法
int lengthOfLIS(int[] nums)
{
    int[] dp = new int[nums.length];
    // dp 数组全都初始化为 1
    Arrays.fill(dp, 1);
    for (int i = 0; i < nums.length; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (nums[i] > nums[j])
                dp[i] = Math.max(dp[i], dp[j] + 1);
        }
    }

    int res = 0;
    for (int i = 0; i < dp.length; i++)
    {
        res = Math.max(res, dp[i]);
    }
    return res;
}

// 经典动态规划问题：高楼扔鸡蛋
// 今天要聊一个很经典的算法问题，若干层楼，若干个鸡蛋，让你算出最少的尝试次数，找到鸡蛋恰好摔不碎的那层楼。国内大厂以及谷歌脸书面试都经常考察这道题，只不过他们觉得扔鸡蛋太浪费，改成扔杯子，扔破碗什么的。
// 具体的问题等会再说，但是这道题的解法技巧很多，光动态规划就好几种效率不同的思路，最后还有一种极其高效数学解法。秉承咱们号一贯的作风，拒绝奇技淫巧，拒绝过于诡异的技巧，因为这些技巧无法举一反三，学了也不划算。
// 下面就来用我们一直强调的动态规划通用思路来研究一下这道题。
// 一、解析题目
// 题目是这样：你面前有一栋从 1 到 N 共 N 层的楼，然后给你 K 个鸡蛋（K 至少为 1）。
// 现在确定这栋楼存在楼层 0 <= F <= N，在这层楼将鸡蛋扔下去，鸡蛋恰好没摔碎（高于 F 的楼层都会碎，低于 F 的楼层都不会碎）。
// 现在问你，最坏情况下，你至少要扔几次鸡蛋，才能确定这个楼层 F 呢？

def superEggDrop(int egg_num, int floor_num)
{
    DP[egg_num][floor_num];
    for (int i = 1; i <= floor_num; i++)
    {
        DP[egg_num][i] = min(DP[egg_num - 1][floor_num - 1], // 鸡蛋碎了
                             DP[egg_num][floor_num + 1]      // 鸡蛋没碎
                             ) +
                         1;
    }
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// 最长公共子序列
// 最长公共子序列（Longest Common Subsequence，简称 LCS）是一道非常经典的面试题目，因为它的解法是典型的二维动态规划，大部分比较困难的字符串问题都和这个问题一个套路，比如说编辑距离。而且，这个算法稍加改造就可以用于解决其他问题，
// 所以说 LCS 算法是值得掌握的。
// 题目就是让我们求两个字符串的 LCS 长度：

// 输入: str1 = "abcde", str2 = "ace"
// 输出: 3
// 解释: 最长公共子序列是 "ace"，它的长度是 3
// 肯定有读者会问，为啥这个问题就是动态规划来解决呢？因为子序列类型的问题，穷举出所有可能的结果都不容易，而动态规划算法做的就是穷举 + 剪枝，它俩天生一对儿。所以可以说只要涉及子序列问题，十有八九都需要动态规划来解决，往这方面考虑就对了。

// 下面就来手把手分析一下，这道题目如何用动态规划技巧解决
int longestCommonSubsequence(string str1, string str2)
{
    int m = str1.size();
    int n = str2.size();
    vector<vector<int>> DP(m, vector<int>(n, 0) >);
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (str1[i] == str2[j])
            { //找到一个 lcs 中的字符
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else
            {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[-1][-1]; //最后一个
}

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// https://github.com/lucianzhong/fucking-algorithm/blob/master/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%B3%BB%E5%88%97/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E4%B9%8B%E6%AD%A3%E5%88%99%E8%A1%A8%E8%BE%BE.md
// 动态规划之正则表达
// 给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

// ‘.’ 匹配任意单个字符
// ‘*’ 匹配零个或多个前面的那一个元素
// 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

// 说明:

// s 可能为空，且只包含从 a-z 的小写字母。
// p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
// 示例 1:

// 输入:
// s = "aa"
// p = "a"
// 输出: false
// 解释: "a" 无法匹配 "aa" 整个字符串。
// 示例 2:

// 输入:
// s = "aa"
// p = "a*"
// 输出: true
// 解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
// 示例 3:

// 输入:
// s = "ab"
// p = ".*"
// 输出: true
// 解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
// 示例 4:

// 输入:
// s = "aab"
// p = "c*a*b"
// 输出: true
// 解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
// 示例 5:

// 输入:
// s = "mississippi"
// p = "mis*is*p*."
// 输出: false

// 第一步，我们暂时不管正则符号，如果是两个普通的字符串进行比较，如何进行匹配？
// def isMatch(text, pattern) -> bool:
//     if pattern is empty: return (text is empty?)
//     first_match = (text not empty) and pattern[0] == text[0]
//     return first_match and isMatch(text[1:], pattern[1:])

// 二、处理点号「.」通配符
// 点号可以匹配任意一个字符，万金油嘛，其实是最简单的，稍加改造即可：

// def isMatch(text, pattern) -> bool:
//     if not pattern: return not text
//     first_match = bool(text) and pattern[0] in
// {
//     text[0], '.'
// }
// return first_match and isMatch(text [1:], pattern [1:])

//                                三、处理「*」通配符
//                                               星号通配符可以让前一个字符重复任意次数，包括零次。那到底是重复几次呢？这似乎有点困难，不过不要着急，我们起码可以把框架的搭建再进一步：

//                                                   def isMatch(text, pattern)
//                                                       ->bool : if not pattern : return not text
//                                                                                     first_match = bool(text) and pattern[0] in
// {
//     text[0], '.'
// }
// if
//     len(pattern) >= 2 and pattern[1] == '*' :
// #发现 '*' 通配符
//         else : return first_match
//             and isMatch(text [1:], pattern [1:])

//                         星号前面的那个字符到底要重复几次呢？这需要计算机暴力穷举来算，假设重复 N 次吧。前文多次强调过，写递归的技巧是管好当下，之后的事抛给递归。具体到这里，不管 N 是多少，当前的选择只有两个：匹配 0 次、匹配 1 次。所以可以这样处理：

//                     if len(pattern) >= 2 and
//             pattern[1] == '*' : return isMatch(text, pattern [2:]) or
//         first_match and isMatch(text [1:], pattern)
// #解释：如果发现有字符和 '*' 结合，
// #或者匹配该字符 0 次，然后跳过该字符和 '*'
// #或者当 pattern[0] 和 text[0] 匹配后，移动 text

// #暴力递归
//                             def isMatch(text, pattern)
//                                 ->bool : if not pattern : return not text

//                                                           first = bool(text) and pattern[0] in
//     {
//         text[0], '.'
//     }

// if
//     len(pattern) >= 2 and pattern[1] == '*' : return isMatch(text, pattern [2:]) or first and isMatch(text [1:], pattern) else : return first and isMatch(text [1:], pattern [1:])

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// https : //github.com/lucianzhong/fucking-algorithm/blob/master/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%B3%BB%E5%88%97/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E4%B9%8B%E5%9B%9B%E9%94%AE%E9%94%AE%E7%9B%98.md

// 4键键盘（DP，Ctrl + CV）
// 1. 题目 假设你有一个特殊的键盘包含下面的按键：
// Key 1 : (A)：在屏幕上打印一个 'A'
// Key 2 : (Ctrl - A) ：选中整个屏幕
// Key 3 : (Ctrl - C) ：复制选中区域到缓冲区
// Key 4 : (Ctrl - V) ：将缓冲区内容输出到上次输入的结束位置，并显示在屏幕上。 现在，你只可以按键 N 次（使用上述四种按键），请问屏幕上最多可以显示几个 'A’呢？

// 样例 1 : 输入 : N = 3 输出 : 3 解释 : 我们最多可以在屏幕上显示三个 'A'通过如下顺序按键： A,A, A
// 样例 2 : 输入 : N = 7 输出 : 9 解释 : 我们最多可以在屏幕上显示九个 'A'通过如下顺序按键： A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V 注释 : 1 <= N <= 50 结果不会超过 32 位有符号整数范围。

int maxA(int N)
{
    int[] dp = new int[N + 1];
    dp[0] = 0;
    for (int i = 1; i <= N; i++)
    {
        // 按 A 键
        dp[i] = dp[i - 1] + 1;
        for (int j = 2; j < i; j++)
        {
            // 全选 & 复制 dp[j-2]，连续粘贴 i - j 次
            // 屏幕上共 dp[j - 2] * (i - j + 1) 个 A
            dp[i] = Math.max(dp[i], dp[j - 2] * (i - j + 1));
        }
    }
    // N 次按键之后最多有几个 A？
    return dp[N];
}

//////////////////////////////////////////////////////////////////////////////////////////////////////

// House Robber I
// 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
// 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
//  示例 1：
//  输入：[1, 2, 3, 1] 输出：4
//  解释：偷窃 1 号房屋(金额 = 1) ，然后偷窃 3 号房屋(金额 = 3)。
//  偷窃到的最高金额 = 1 + 3 = 4 。 示例 2：
//  输入：[2, 7, 9, 3, 1] 输出：12
//  解释：偷窃 1 号房屋(金额 = 2),
//  偷窃 3 号房屋(金额 = 9) ，接着偷窃 5 号房屋(金额 = 1)。
//  偷窃到的最高金额 = 2 + 9 + 1 = 12 。
//  这道题的本质相当于在一列数组中取出一个或多个不相邻数，使其和最大。那么对于这类求极值的问题首先考虑动态规划 Dynamic Programming 来解，维护一个一位数组 dp，其中 dp[i] 表示[0, i] 区间可以抢夺的最大值，对当前i来说，
//  有抢和不抢两种互斥的选择，不抢即为 dp[i - 1] （等价于去掉 nums[i] 只抢[0, i - 1] 区间最大值），抢即为 dp[i - 2] + nums[i] （等价于去掉 nums[i - 1] ）
// 再举一个简单的例子来说明一下吧，比如说 nums为{3, 2, 1, 5} ，那么来看 dp 数组应该是什么样的，首先 dp[0] = 3 没啥疑问，再看 dp[1] 是多少呢，由于3比2大，所以抢第一个房子的3，当前房子的2不抢，则dp[1] = 3，那么再来看 dp[2] ，
// 由于不能抢相邻的，所以可以用再前面的一个的 dp 值加上当前的房间值，和当前房间的前面一个 dp 值比较，取较大值当做当前 dp 值，这样就可以得到状态转移方程 dp[i] = max(num[i] + dp[i - 2], dp[i - 1]),
// 且需要初始化 dp[0] 和 dp[1] ，其中 dp[0] 即为 num[0] ，dp[1] 此时应该为 max(num[0], num[1]) ，代码如下：

int rob(vector<int> &nums)
{
    if (nums.size() <= 1)
        return nums.empty() ? 0 : nums[0];
    vector<int> dp = {nums[0], max(nums[0], nums[1])};
    for (int i = 2; i < nums.size(); ++i)
    {
        dp.push_back(max(nums[i] + dp[i - 2], dp[i - 1]));
    }
    return dp.back();
}

// 这道题是之前那道 House Robber 的拓展，现在房子排成了一个圆圈，则如果抢了第一家，就不能抢最后一家，因为首尾相连了，所以第一家和最后一家只能抢其中的一家，或者都不抢，那这里变通一下，
// 如果把第一家和最后一家分别去掉，各算一遍能抢的最大值，然后比较两个值取其中较大的一个即为所求。那只需参考之前的 House Robber 中的解题方法，然后调用两边取较大值，代码如下：

int rob(vector<int> &nums)
{
    if (nums.size() <= 1)
        return nums.empty() ? 0 : nums[0];
    return max(rob(nums, 0, nums.size() - 1), rob(nums, 1, nums.size()));
}
int rob(vector<int> &nums, int left, int right)
{
    if (right - left <= 1)
        return nums[left];
    vector<int> dp(right, 0);
    dp[left] = nums[left];
    dp[left + 1] = max(nums[left], nums[left + 1]);
    for (int i = left + 2; i < right; ++i)
    {
        dp[i] = max(nums[i] + dp[i - 2], dp[i - 1]);
    }
    return dp.back();
}

// House Robber III
//         第三题又想法设法地变花样了，此强盗发现现在面对的房子不是一排，不是一圈，而是一棵二叉树！房子在二叉树的节点上，相连的两个房子不能同时被抢劫，果然是传说中的高智商犯罪
//             如果隔一个偷，那么是 4 +
//     2 = 6，其实最优解应为 4 + 3 = 7，隔了两个，所以说纯粹是怎么多怎么来，那么这种问题是很典型的递归问题，可以利用回溯法来做，因为当前的计算需要依赖之前的结果，那么对于某一个节点，如果其左子节点存在，通过递归调用函数，算出不包含左子节点返回的值，同理，如果右子节点存在，算出不包含右子节点返回的值，那么此节点的最大值可能有两种情况，一种是该节点值加上不包含左子节点和右子节点的返回值之和，另一种是左右子节点返回值之和不包含当期节点值，取两者的较大值返回即可，但是这种方法无法通过 OJ，超时了，所以必须优化这种方法，这种方法重复计算了很多地方，比如要完成一个节点的计算，就得一直找左右子节点计算，可以把已经算过的节点用 HashMap 保存起来，以后递归调用的时候，现在 HashMap 里找，如果存在直接返回，如果不存在，等计算出来后，保存到 HashMap 中再返回，这样方便以后再调用，参见代码如下：

//             解法一：

//                 复制代码 class Solution
// {
// public:
//     int rob(TreeNode *root)
//     {
//         unordered_map<TreeNode *, int> m;
//         return dfs(root, m);
//     }
//     int dfs(TreeNode *root, unordered_map<TreeNode *, int> &m)
//     {
//         if (!root)
//             return 0;
//         if (m.count(root))
//             return m[root];
//         int val = 0;
//         if (root->left)
//         {
//             val += dfs(root->left->left, m) + dfs(root->left->right, m);
//         }
//         if (root->right)
//         {
//             val += dfs(root->right->left, m) + dfs(root->right->right, m);
//         }
//         val = max(val + root->val, dfs(root->left, m) + dfs(root->right, m));
//         m[root] = val;
//         return val;
//     }
// };

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// 贪心算法之区间调度问题
// 言归正传，本文解决一个很经典的贪心算法问题 Interval Scheduling（区间调度问题）。给你很多形如 [start, end] 的闭区间，请你设计一个算法，算出这些区间中最多有几个互不相交的区间。

// int intervalSchedule(int[][] intvs) {}
// 举个例子，intvs = [[1,3], [2,4], [3,6]]，这些区间最多有 2 个区间互不相交，即 [[1,3], [3,6]]，你的算法应该返回 2。注意边界相同并不算相交。

// 这个问题在生活中的应用广泛，比如你今天有好几个活动，每个活动都可以用区间 [start, end] 表示开始和结束的时间，请问你今天**最多能参加几个活动呢？**显然你一个人不能同时参加两个活动，所以说这个问题就是求这些时间区间的最大不相交子集。

// 二、贪心解法
// 这个问题有许多看起来不错的贪心思路，却都不能得到正确答案。比如说：

// 也许我们可以每次选择可选区间中开始最早的那个？但是可能存在某些区间开始很早，但是很长，使得我们错误地错过了一些短的区间。或者我们每次选择可选区间中最短的那个？或者选择出现冲突最少的那个区间？这些方案都能很容易举出反例，不是正确的方案。

// 正确的思路其实很简单，可以分为以下三步：

// 从区间集合 intvs 中选择一个区间 x，这个 x 是在当前所有区间中结束最早的（end 最小）。
// 把所有与 x 区间相交的区间从区间集合 intvs 中删除。
// 重复步骤 1 和 2，直到 intvs 为空为止。之前选出的那些 x 就是最大不相交子集。

int intervalSchedule(int[][] intvs) {
    if (intvs.length == 0) return 0;
    // 按 end 升序排序
    Arrays.sort(intvs, new Comparator<int[]>() {
        public int compare(int[] a, int[] b) {
            return a[1] - b[1];
        }
    });
    // 至少有一个区间不相交
    int count = 1;
    // 排序后，第一个区间就是 x
    int x_end = intvs[0][1];
    for (int[] interval : intvs) {
        int start = interval[0];
        if (start >= x_end) {
            // 找到下一个选择的区间了
            count++;
            x_end = interval[1];
        }
    }
    return count;
}



// 给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠
// 注意:
// 可以认为区间的终点总是大于它的起点。
// 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
// 示例 1:
// 输入: [ [1,2], [2,3], [3,4], [1,3] ]
// 输出: 1
// 解释: 移除 [1,3] 后，剩下的区间没有重叠


int eraseOverlapIntervals(int[][] intervals) {
    int n = intervals.length;
    return n - intervalSchedule(intervals); // 我们已经会求最多有几个区间不会重叠了，那么剩下的不就是至少需要去除的区间吗？
}



//////////////////////////////////////////////////////////////////////////////////////////////////
// BFS and DFS
// bfs＝队列，入队列，出队列
// dfs=栈，压栈，出栈
// 深度优先一般是解决连通性问题，而广度优先一般是解决最短路径问题




////////////////////////////////////////////////////////////////////////////
// 团灭 LeetCode 股票买卖问题
// 三维 DP
// https://github.com/lucianzhong/fucking-algorithm/blob/master/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%B3%BB%E5%88%97/%E5%9B%A2%E7%81%AD%E8%82%A1%E7%A5%A8%E9%97%AE%E9%A2%98.md

// 这个问题的「状态」有三个，第一个是天数，第二个是允许交易的最大次数，第三个是当前的持有状态（即之前说的 rest 的状态，我们不妨用 1 表示持有，0 表示没有持有）。然后我们用一个三维数组就可以装下这几种状态的全部组合：

// dp[i][k][0 or 1]
// 0 <= i <= n-1, 1 <= k <= K
// n 为天数，大 K 为最多交易数
// 此问题共 n × K × 2 种状态，全部穷举就能搞定。

for 0 <= i < n:
    for 1 <= k <= K:
        for s in {0, 1}:
            dp[i][k][s] = max(buy, sell, rest)


// 而且我们可以用自然语言描述出每一个状态的含义，比如说 dp[3][2][1] 的含义就是：今天是第三天，我现在手上持有着股票，至今最多进行 2 次交易。再比如 dp[2][3][0] 的含义：今天是第二天，我现在手上没有持有股票，至今最多进行 3 次交易。很容易理解，对吧？
// 我们想求的最终答案是 dp[n - 1][K][0]，即最后一天，最多允许 K 次交易，最多获得多少利润。读者可能问为什么不是 dp[n - 1][K][1]？因为 [1] 代表手上还持有股票，[0] 表示手上的股票已经卖出去了，很显然后者得到的利润一定大于前者

// 通过这个图可以很清楚地看到，每种状态（0 和 1）是如何转移而来的。根据这个图，我们来写一下状态转移方程:

dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
              max(   选择 rest  ,             选择 sell      )

// 解释：今天我没有持有股票，有两种可能:
// 要么是我昨天就没有持有，然后今天选择 rest，所以我今天还是没有持有；
// 要么是我昨天持有股票，但是今天我 sell 了，所以我今天没有持有股票了。

dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
              max(   选择 rest  ,           选择 buy         )

// 解释：今天我持有着股票，有两种可能:
// 要么我昨天就持有着股票，然后今天选择 rest，所以我今天还持有着股票；
// 要么我昨天本没有持有，但今天我选择 buy，所以今天我就持有股票了。
// 这个解释应该很清楚了，如果 buy，就要从利润中减去 prices[i]，如果 sell，就要给利润增加 prices[i]。今天的最大利润就是这两种可能选择中较大的那个。
// 而且注意 k 的限制，我们在选择 buy 的时候，把 k 减小了 1，很好理解吧，当然你也可以在 sell 的时候减 1，一样的。

// 现在，我们已经完成了动态规划中最困难的一步:状态转移方程。
// 如果之前的内容你都可以理解，那么你已经可以秒杀所有问题了，只要套这个框架就行了。不过还差最后一点点，就是定义 base case，即最简单的情况。

dp[-1][k][0] = 0
// 解释：因为 i 是从 0 开始的，所以 i = -1 意味着还没有开始，这时候的利润当然是 0
dp[-1][k][1] = -infinity
// 解释：还没开始的时候，是不可能持有股票的，用负无穷表示这种不可能。
dp[i][0][0] = 0
// 解释：因为 k 是从 1 开始的，所以 k = 0 意味着根本不允许交易，这时候利润当然是 0
dp[i][0][1] = -infinity
// 解释：不允许交易的情况下，是不可能持有股票的，用负无穷表示这种不可能

// 把上面的状态转移方程总结一下:
// base case:
dp[-1][k][0] = dp[i][0][0] = 0
dp[-1][k][1] = dp[i][0][1] = -infinity

// 状态转移方程：
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
// 读者可能会问，这个数组索引是 -1 怎么编程表示出来呢，负无穷怎么表示呢？这都是细节问题，有很多方法实现。现在完整的框架已经完成，下面开始具体化。


// k = +infinity with cooldown
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-2][k-1][0] - prices[i])
// 解释：第 i 天选择 buy 的时候，要从 i-2 的状态转移，而不是 i-1

// k = +infinity with fee
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i] - fee)





///////////////////////////////////////////////////////////////////////////////////////////
// LRU 算法
// LRU 缓存淘汰算法就是一种常用策略。LRU 的全称是 Least Recently Used，也就是说我们认为最近使用过的数据应该是是「有用的」，很久都没用过的数据应该是无用的，内存满了就优先删那些很久没用过的数据
// https://github.com/lucianzhong/fucking-algorithm/blob/master/%E9%AB%98%E9%A2%91%E9%9D%A2%E8%AF%95%E7%B3%BB%E5%88%97/LRU%E7%AE%97%E6%B3%95.md

// LRU 算法实际上是让你设计数据结构：首先要接收一个 capacity 参数作为缓存的最大容量，然后实现两个 API，一个是 put(key, val) 方法存入键值对，另一个是 get(key) 方法获取 key 对应的 val，如果 key 不存在则返回 -1
// 注意哦，get 和 put 方法必须都是 $O(1)$ 的时间复杂度，我们举个具体例子来看看 LRU 算法怎么工作

/* 缓存容量为 2 */
LRUCache cache = new LRUCache(2); // 你可以把 cache 理解成一个队列,假设左边是队头，右边是队尾,最近使用的排在队头，久未使用的排在队尾,圆括号表示键值对 (key, val)

cache.put(1, 1); // cache = [(1, 1)]
cache.put(2, 2); // cache = [(2, 2), (1, 1)]
cache.get(1);       // 返回 1  // cache = [(1, 1), (2, 2)] // 解释：因为最近访问了键 1，所以提前至队头 // 返回键 1 对应的值 1
cache.put(3, 3);  // cache = [(3, 3), (1, 1)] // 解释：缓存容量已满，需要删除内容空出位置,优先删除久未使用的数据，也就是队尾的数据,然后把新的数据插入队头
cache.get(2);       // 返回 -1 (未找到), cache = [(3, 3), (1, 1)] // 解释：cache 中不存在键为 2 的数据
cache.put(1, 4);    // cache = [(1, 4), (3, 3)], 解释：键 1 已存在，把原始值 1 覆盖为 4, 不要忘了也要将键值对提前到队头


class Node {
    public int key, val;
    public Node next, prev;
    public Node(int k, int v) {
        this.key = k;
        this.val = v;
    }
}
// 然后依靠我们的 Node 类型构建一个双链表，实现几个需要的 API（这些操作的时间复杂度均为 $O(1)$)：

// 双向列表
class DoubleList {  
    // 在链表头部添加节点 x，时间 O(1)
    public void addFirst(Node x);

    // 删除链表中的 x 节点（x 一定存在）,由于是双链表且给的是目标 Node 节点，时间 O(1)
    public void remove(Node x);
    
    // 删除链表中最后一个节点，并返回该节点，时间 O(1)
    public Node removeLast();
    
    // 返回链表长度，时间 O(1)
    public int size();
}
// PS：这就是普通双向链表的实现，为了让读者集中精力理解 LRU 算法的逻辑，就省略链表的具体代码。


// 有了双向链表的实现，我们只需要在 LRU 算法中把它和哈希表结合起来即可。我们先把逻辑理清楚:

// key 映射到 Node(key, val)
unordered_map<Integer, Node> map;
// Node(k1, v1) <-> Node(k2, v2)...
DoubleList cache;

int get(int key) {
    if (key 不存在) {
        return -1;
    } else {        
        将数据 (key, val) 提到开头；
        return val;
    }
}

void put(int key, int val) {
    Node x = new Node(key, val);
    if (key 已存在) {
        把旧的数据删除；
        将新节点 x 插入到开头；
    } else {
        if (cache 已满) {
            删除链表的最后一个数据腾位置；
            删除 map 中映射到该数据的键；
        } 
        将新节点 x 插入到开头；
        map 中新建 key 对新节点 x 的映射；
    }
}


// 如果能够看懂上述逻辑，翻译成代码就很容易理解了:

class LRUCache {
    // key -> Node(key, val)
    private unordered_map<Integer, Node> map;
    // Node(k1, v1) <-> Node(k2, v2)...
    private DoubleList cache;
    // 最大容量
    private int cap;
    
    public LRUCache(int capacity) {
        this.cap = capacity;
        map = new unordered_map<>();
        cache = new DoubleList();
    }
    
    public int get(int key) {
        if (!map.containsKey(key))
            return -1;
        int val = map.get(key).val;
        // 利用 put 方法把该数据提前
        put(key, val);
        return val;
    }
    
    public void put(int key, int val) {
        // 先把新节点 x 做出来
        Node x = new Node(key, val);
        
        if (map.containsKey(key)) {
            // 删除旧的节点，新的插到头部
            cache.remove(map.get(key));
            cache.addFirst(x);
            // 更新 map 中对应的数据
            map.put(key, x);
        } else {
            if (cap == cache.size()) {
                // 删除链表最后一个数据
                Node last = cache.removeLast();
                map.remove(last.key);
            }
            // 直接添加到头部
            cache.addFirst(x);
            map.put(key, x);
        }
    }
}
// 这里就能回答之前的问答题“为什么要在链表中同时存储 key 和 val，而不是只存储 val”，注意这段代码:

if (cap == cache.size()) {
    // 删除链表最后一个数据
    Node last = cache.removeLast();
    map.remove(last.key);
}


// 当缓存容量已满，我们不仅仅要删除最后一个 Node 节点，还要把 map 中映射到该节点的 key 同时删除，
// 而这个 key 只能由 Node 得到。如果 Node 结构中只存储 val，那么我们就无法得知 key 是什么，就无法删除 map 中的键，造成错误
// 至此，你应该已经掌握 LRU 算法的思想和实现了，很容易犯错的一点是:处理链表节点的同时不要忘了更新哈希表中对节点的映射












/////////////////////////////////////////////////////////////////////////////////////////////////
// 常用的位操作
// https://github.com/lucianzhong/fucking-algorithm/blob/master/%E7%AE%97%E6%B3%95%E6%80%9D%E7%BB%B4%E7%B3%BB%E5%88%97/%E5%B8%B8%E7%94%A8%E7%9A%84%E4%BD%8D%E6%93%8D%E4%BD%9C.md

// 判断两个数是否异号
int x = -1, y = 2;
bool f = ((x ^ y) < 0); // true

int x = 3, y = 2;
bool f = ((x ^ y) < 0); // false
// 这个技巧还是很实用的，利用的是补码编码的符号位。如果不用位运算来判断是否异号，需要使用 if else 分支，还挺麻烦的。读者可能想利用乘积或者商来判断两个数是否异号，但是这种处理方式可能造成溢出，从而出现错误

// 判断一个数是不是 2 的指数
// 一个数如果是 2 的指数，那么它的二进制表示一定只含有一个 1：
// 2^0 = 1 = 0b0001
// 2^1 = 2 = 0b0010
// 2^2 = 4 = 0b0100
// 如果使用位运算技巧就很简单了（注意运算符优先级，括号不可以省略）
bool isPowerOfTwo(int n) {
    if (n <= 0) return false;
    return (n & (n - 1)) == 0;
}




//////////////////////////////////////////////////////////////////////////////////
// 子集排列组合
// https://github.com/lucianzhong/fucking-algorithm/blob/master/%E9%AB%98%E9%A2%91%E9%9D%A2%E8%AF%95%E7%B3%BB%E5%88%97/%E5%AD%90%E9%9B%86%E6%8E%92%E5%88%97%E7%BB%84%E5%90%88.md
// 天就来聊三道考察频率高，而且容易让人搞混的算法问题，分别是求子集（subset），求排列（permutation），求组合（combination）
// 这几个问题都可以用回溯算法模板解决，同时子集问题还可以用数学归纳思想解决。读者可以记住这几个问题的回溯套路，就不怕搞不清了

// result = []
// def backtrack(路径, 选择列表):
//     if 满足结束条件:
//         result.add(路径)
//         return
//     for 选择 in 选择列表:
//         做选择
//         backtrack(路径, 选择列表)
//         撤销选择

// 一. 子集
// 问题很简单，输入一个不包含重复数字的数组，要求算法输出这些数字的所有子集。


vector<vector<int>> subsets(vector<int>& nums);

// 只要改造回溯算法的模板就行了：

vector<vector<int>> res;
vector<vector<int>> subsets(vector<int>& nums) {
    // 记录走过的路径
    vector<int> track;
    backtrack(nums, 0, track);
    return res;
}

void backtrack(vector<int>& nums, int start, vector<int>& track) {
    res.push_back(track);
    for (int i = start; i < nums.size(); i++) {
        // 做选择
        track.push_back(nums[i]);
        // 回溯
        backtrack(nums, i + 1, track);
        // 撤销选择
        track.pop_back();
    }
}

// 二. 组合
// 输入两个数字 n, k，算法输出 [1..n] 中 k 个数字的所有组合。
// 比如输入 n = 4, k = 2，输出如下结果，顺序无所谓，但是不能包含重复（按照组合的定义，[1,2] 和 [2,1] 也算重复）
// [ [1,2], [1,3], [1,4], [2,3], [2,4], [3,4] ]
// 这也是典型的回溯算法，k 限制了树的高度，n 限制了树的宽度，继续套我们以前讲过的回溯算法模板框架就行了：
vector<vector<int>> combine(int n, int k);
vector<vector<int>>res;
vector<vector<int>> combine(int n, int k) {
    if (k <= 0 || n <= 0) return res;
    vector<int> track;
    backtrack(n, k, 1, track);
    return res;
}

void backtrack(int n, int k, int start, vector<int>& track) {
    // 到达树的底部
    if (k == track.size()) {
        res.push_back(track);
        return;
    }
    // 注意 i 从 start 开始递增
    for (int i = start; i <= n; i++) {
        // 做选择
        track.push_back(i);
        backtrack(n, k, i + 1, track);
        // 撤销选择
        track.pop_back();
    }
}


// 三. 排列
// 输入一个不包含重复数字的数组 nums，返回这些数字的全部排列

vector<vector<int>> permute(vector<int>& nums);
// 比如说输入数组 [1,2,3]，输出结果应该如下，顺序无所谓，不能有重复
// [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
// 「回溯算法详解」中就是拿这个问题来解释回溯模板的。


List<List<Integer>> res = new LinkedList<>();

/* 主函数，输入一组不重复的数字，返回它们的全排列 */
List<List<Integer>> permute(int[] nums) {
    // 记录「路径」
    LinkedList<Integer> track = new LinkedList<>();
    backtrack(nums, track);
    return res;
}

void backtrack(int[] nums, LinkedList<Integer> track) {
    // 触发结束条件
    if (track.size() == nums.length) {
        res.add(new LinkedList(track));
        return;
    }
    
    for (int i = 0; i < nums.length; i++) {
        // 排除不合法的选择
        if (track.contains(nums[i]))
            continue;
        // 做选择
        track.add(nums[i]);
        // 进入下一层决策树
        backtrack(nums, track);
        // 取消选择
        track.removeLast();
    }
}


// 回溯模板依然没有变，但是根据排列问题和组合问题画出的树来看，排列问题的树比较对称，而组合问题的树越靠右节点越少。
// 在代码中的体现就是，排列问题每次通过 contains 方法来排除在 track 中已经选择过的数字,而组合问题通过传入一个 start 参数，来排除 start 索引之前的数字
// 以上，就是排列组合和子集三个问题的解法，总结一下:
// 子集问题可以利用数学归纳思想，假设已知一个规模较小的问题的结果，思考如何推导出原问题的结果。也可以用回溯算法，要用 start 参数排除已选择的数字
// 组合问题利用的是回溯思想，结果可以表示成树结构，我们只要套用回溯算法模板即可，关键点在于要用一个 start 排除已经选择过的数字
// 排列问题是回溯思想，也可以表示成树结构套用算法模板，关键点在于使用 contains 方法排除已经选择的数字，前文有详细分析，这里主要是和组合问题作对比
// 记住这几种树的形状，就足以应对大部分回溯算法问题了，无非就是 start 或者 contains 剪枝，也没啥别的技巧了




// 设计Twitter
// https://github.com/lucianzhong/fucking-algorithm/blob/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%B3%BB%E5%88%97/%E8%AE%BE%E8%AE%A1Twitter.md

「design Twitter」是 LeetCode 上第 355 道题目，不仅题目本身很有意思，而且把合并多个有序链表的算法和面向对象设计（OO design）结合起来了，很有实际意义，本文就带大家来看看这道题。

至于 Twitter 的什么功能跟算法有关系，等我们描述一下题目要求就知道了。

一、题目及应用场景简介
Twitter 和微博功能差不多，我们主要要实现这样几个 API：

class Twitter {

    /** user 发表一条 tweet 动态 */
    public void postTweet(int userId, int tweetId) {}
    
    /** 返回该 user 关注的人（包括他自己）最近的动态 id，
    最多 10 条，而且这些动态必须按从新到旧的时间线顺序排列。*/
    public List<Integer> getNewsFeed(int userId) {}
    
    /** follower 关注 followee，如果 Id 不存在则新建 */
    public void follow(int followerId, int followeeId) {}
    
    /** follower 取关 followee，如果 Id 不存在则什么都不做 */
    public void unfollow(int followerId, int followeeId) {}
}
举个具体的例子，方便大家理解 API 的具体用法：

Twitter twitter = new Twitter();

twitter.postTweet(1, 5);
// 用户 1 发送了一条新推文 5

twitter.getNewsFeed(1);
// return [5]，因为自己是关注自己的

twitter.follow(1, 2);
// 用户 1 关注了用户 2

twitter.postTweet(2, 6);
// 用户2发送了一个新推文 (id = 6)

twitter.getNewsFeed(1);
// return [6, 5]
// 解释：用户 1 关注了自己和用户 2，所以返回他们的最近推文
// 而且 6 必须在 5 之前，因为 6 是最近发送的

twitter.unfollow(1, 2);
// 用户 1 取消关注了用户 2

twitter.getNewsFeed(1);
// return [5]
这个场景在我们的现实生活中非常常见。拿朋友圈举例，比如我刚加到女神的微信，然后我去刷新一下我的朋友圈动态，那么女神的动态就会出现在我的动态列表，而且会和其他动态按时间排好序。只不过 Twitter 是单向关注，微信好友相当于双向关注。除非，被屏蔽...

这几个 API 中大部分都很好实现，最核心的功能难点应该是 getNewsFeed，因为返回的结果必须在时间上有序，但问题是用户的关注是动态变化的，怎么办？

这里就涉及到算法了：如果我们把每个用户各自的推文存储在链表里，每个链表节点存储文章 id 和一个时间戳 time（记录发帖时间以便比较），而且这个链表是按 time 有序的，那么如果某个用户关注了 k 个用户，我们就可以用合并 k 个有序链表的算法合并出有序的推文列表，正确地 getNewsFeed 了！

具体的算法等会讲解。不过，就算我们掌握了算法，应该如何编程表示用户 user 和推文动态 tweet 才能把算法流畅地用出来呢？这就涉及简单的面向对象设计了，下面我们来由浅入深，一步一步进行设计。

二、面向对象设计
根据刚才的分析，我们需要一个 User 类，储存 user 信息，还需要一个 Tweet 类，储存推文信息，并且要作为链表的节点。所以我们先搭建一下整体的框架：

class Twitter {
    private static int timestamp = 0;
    private static class Tweet {}
    private static class User {}

    /* 还有那几个 API 方法 */
    public void postTweet(int userId, int tweetId) {}
    public List<Integer> getNewsFeed(int userId) {}
    public void follow(int followerId, int followeeId) {}
    public void unfollow(int followerId, int followeeId) {}
}
之所以要把 Tweet 和 User 类放到 Twitter 类里面，是因为 Tweet 类必须要用到一个全局时间戳 timestamp，而 User 类又需要用到 Tweet 类记录用户发送的推文，所以它们都作为内部类。不过为了清晰和简洁，下文会把每个内部类和 API 方法单独拿出来实现。

1、Tweet 类的实现

根据前面的分析，Tweet 类很容易实现：每个 Tweet 实例需要记录自己的 tweetId 和发表时间 time，而且作为链表节点，要有一个指向下一个节点的 next 指针。

class Tweet {
    private int id;
    private int time;
    private Tweet next;

    // 需要传入推文内容（id）和发文时间
    public Tweet(int id, int time) {
        this.id = id;
        this.time = time;
        this.next = null;
    }
}



2、User 类的实现

我们根据实际场景想一想，一个用户需要存储的信息有 userId，关注列表，以及该用户发过的推文列表。其中关注列表应该用集合（Hash Set）这种数据结构来存，因为不能重复，而且需要快速查找；推文列表应该由链表这种数据结构储存，以便于进行有序合并的操作。画个图理解一下：

除此之外，根据面向对象的设计原则，「关注」「取关」和「发文」应该是 User 的行为，况且关注列表和推文列表也存储在 User 类中，所以我们也应该给 User 添加 follow，unfollow 和 post 这几个方法：

// static int timestamp = 0
class User {
    private int id;
    public Set<Integer> followed;
    // 用户发表的推文链表头结点
    public Tweet head;

    public User(int userId) {
        followed = new HashSet<>();
        this.id = userId;
        this.head = null;
        // 关注一下自己
        follow(id);
    }

    public void follow(int userId) {
        followed.add(userId);
    }

    public void unfollow(int userId) {
        // 不可以取关自己
        if (userId != this.id)
            followed.remove(userId);
    }

    public void post(int tweetId) {
        Tweet twt = new Tweet(tweetId, timestamp);
        timestamp++;
        // 将新建的推文插入链表头
        // 越靠前的推文 time 值越大
        twt.next = head;
        head = twt;
    }
}
3、几个 API 方法的实现

class Twitter {
    private static int timestamp = 0;
    private static class Tweet {...}
    private static class User {...}

    // 我们需要一个映射将 userId 和 User 对象对应起来
    private HashMap<Integer, User> userMap = new HashMap<>();

    /** user 发表一条 tweet 动态 */
    public void postTweet(int userId, int tweetId) {
        // 若 userId 不存在，则新建
        if (!userMap.containsKey(userId))
            userMap.put(userId, new User(userId));
        User u = userMap.get(userId);
        u.post(tweetId);
    }
    
    /** follower 关注 followee */
    public void follow(int followerId, int followeeId) {
        // 若 follower 不存在，则新建
		if(!userMap.containsKey(followerId)){
			User u = new User(followerId);
			userMap.put(followerId, u);
		}
        // 若 followee 不存在，则新建
		if(!userMap.containsKey(followeeId)){
			User u = new User(followeeId);
			userMap.put(followeeId, u);
		}
		userMap.get(followerId).follow(followeeId);
    }
    
    /** follower 取关 followee，如果 Id 不存在则什么都不做 */
    public void unfollow(int followerId, int followeeId) {
        if (userMap.containsKey(followerId)) {
            User flwer = userMap.get(followerId);
            flwer.unfollow(followeeId);
        }
    }

    /** 返回该 user 关注的人（包括他自己）最近的动态 id，
    最多 10 条，而且这些动态必须按从新到旧的时间线顺序排列。*/
    public List<Integer> getNewsFeed(int userId) {
        // 需要理解算法，见下文
    }
}
三、算法设计
实现合并 k 个有序链表的算法需要用到优先级队列（Priority Queue），这种数据结构是「二叉堆」最重要的应用，你可以理解为它可以对插入的元素自动排序。乱序的元素插入其中就被放到了正确的位置，可以按照从小到大（或从大到小）有序地取出元素。

PriorityQueue pq
# 乱序插入
for i in {2,4,1,9,6}:
    pq.add(i)
while pq not empty:
    # 每次取出第一个（最小）元素
    print(pq.pop())

# 输出有序：1,2,4,6,9
借助这种牛逼的数据结构支持，我们就很容易实现这个核心功能了。注意我们把优先级队列设为按 time 属性从大到小降序排列，因为 time 越大意味着时间越近，应该排在前面：

public List<Integer> getNewsFeed(int userId) {
    List<Integer> res = new ArrayList<>();
    if (!userMap.containsKey(userId)) return res;
    // 关注列表的用户 Id
    Set<Integer> users = userMap.get(userId).followed;
    // 自动通过 time 属性从大到小排序，容量为 users 的大小
    PriorityQueue<Tweet> pq = 
        new PriorityQueue<>(users.size(), (a, b)->(b.time - a.time));

    // 先将所有链表头节点插入优先级队列
    for (int id : users) {
        Tweet twt = userMap.get(id).head;
        if (twt == null) continue;
        pq.add(twt);
    }

    while (!pq.isEmpty()) {
        // 最多返回 10 条就够了
        if (res.size() == 10) break;
        // 弹出 time 值最大的（最近发表的）
        Tweet twt = pq.poll();
        res.add(twt.id);
        // 将下一篇 Tweet 插入进行排序
        if (twt.next != null) 
            pq.add(twt.next);
    }
    return res;
}
这个过程是这样的，下面是我制作的一个 GIF 图描述合并链表的过程。假设有三个 Tweet 链表按 time 属性降序排列，我们把他们降序合并添加到 res 中。注意图中链表节点中的数字是 time 属性，不是 id 属性：
至此，这道一个极其简化的 Twitter 时间线功能就设计完毕了。

四、最后总结
本文运用简单的面向对象技巧和合并 k 个有序链表的算法设计了一套简化的时间线功能，这个功能其实广泛地运用在许多社交应用中。

我们先合理地设计出 User 和 Tweet 两个类，然后基于这个设计之上运用算法解决了最重要的一个功能。可见实际应用中的算法并不是孤立存在的，需要和其他知识混合运用，才能发挥实际价值。

当然，实际应用中的社交 App 数据量是巨大的，考虑到数据库的读写性能，我们的设计可能承受不住流量压力，还是有些太简化了。而且实际的应用都是一个极其庞大的工程，比如下图，是 Twitter 这样的社交网站大致的系统结构：